import bean.TreeNode;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 中等
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 * @since 2023-09-19 10:32
 */
public class _114二叉树展开为链表 {
    public void flatten(TreeNode root) {
        if(root == null) return;
        //先序遍历
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode pre = null;
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(pre != null){
                pre.left = null;
                pre.right = cur;
            }
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
            pre = cur;
        }
    }
}
